Міністерство освіти і науки України Національний університет «Львівська політехніка»
Лабораторна робота №2 з дисципліни: «Технології розподілених систем та паралельних обчислень» Варіант - 6
Тема роботи: Розподілене програмування на основі технології MPI.
Мета роботи: Оволодіти практичними прийомами розробки паралельних алгоритмів та розподілених програм за допомогою технології MPІ, дослідити їх переваги при розв’язанні практичних задач.
Завдання: Знаходження шляху на графі з допомогою алгоритму Лі.
Виконання.
Код програми:
#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <dos.h>
#include <windows.h>
#include <mpi.h>
using namespace std;
#include <stdio.h>
#define FALSE 0
#define TRUE 1
#define NROWS 6
#define MCOLS 6
// Symbols:
// '.' = open
// '#' = blocked
// 'S' = start
// 'G' = goal
// '+' = path
// 'x' = bad path
char maze[NROWS][MCOLS] = {
{ 'S', '.', '.', '.', '#', '#' },
{ '#', '.', '#', '.', '.', '.' },
{ '#', '.', '#', '#', '.', '#' },
{ '.', '.', '#', '.', '#', '#' },
{ '#', '.', '.', '.', '#', 'G' },
{ '#', '.', '#', '.', '.', '.' }
};
void display_maze(void);
int find_path(int x, int y);
int main(void)
{
//MPI_Init(&argc, &argv);
//MPI_Comm_size(MPI_COMM_WORLD, &size); // Розмір комунікатора
//MPI_Comm_rank(MPI_COMM_WORLD, &myrank); // Одержуємо наш номер
clock_t t = clock();
display_maze();
if (find_path(0, 0) == TRUE)
printf("Success!\n");
else
printf("Failed\n");
display_maze();
int i;
cin >> i;
clock_t t1 = clock();
cout << "TIME: " << (t1 - t) / 1000 << "ms" << endl;
//MPI_Finalize();
system("pause");
return 0;
}
void display_maze(void)
{
int i;
printf("MAZE:\n");
for (i = 0; i < NROWS; i++)
printf("%.*s\n", MCOLS, maze[i]);
printf("\n");
return;
}
int find_path(int x, int y)
{
// If x,y is outside maze, return false.
if (x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1) return FALSE;
// If x,y is the goal, return true.
if (maze[y][x] == 'G') return TRUE;
// If x,y is not open, return false.
if (maze[y][x] != '.' && maze[y][x] != 'S') return FALSE;
// Mark x,y part of solution path.
maze[y][x] = '+';
// If find_path North of x,y is true, return true.
if (find_path(x, y - 1) == TRUE) return TRUE;
// If find_path East of x,y is true, return true.
if (find_path(x + 1, y) == TRUE) return TRUE;
// If find_path South of x,y is true, return true.
if (find_path(x, y + 1) == TRUE) return TRUE;
// If find_path West of x,y is true, return true.
if (find_path(x - 1, y) == TRUE) return TRUE;
// Unmark x,y as part of solution path.
maze[y][x] = 'x';
return FALSE;
}
Програма в роботі:
Без використання MPI:
/
З використанням MPI:
/
Висновок: на лабораторній роботі було виконано завдання написавши код, який реалізовує алгоритм його виконання. Замінив завдання з методички подібним. Замість пошуку шляху на графі з використанням алгоритму лубі, використав алгоритм лі. В досліді декілька раз виконав запуск програми з mpi і без. По результатах видно, що з використанням
mpi працює швидше. Хоча опрацьовувались не велика кількість даних, але отримано результат.
